Codility Lesson 9 - MaxProfit

문제 설명

N개의 정수로 구성된 배열 A가 주어집니다. 여기에는 연속된 N일 동안의 주식 일별 가격이 포함되어 있습니다. 단일 주식을 P일에 매수하고 Q일에 매도한 경우, 여기서 0 ≤ P ≤ Q < N이면 해당 거래의 수익은 A[Q] ≥ A[P]인 경우 A[Q] - A[P]와 같습니다. 그렇지 않으면 거래는 A[P] - A[Q]의 손실을 가져옵니다.

예를 들어 다음과 같은 6개의 요소로 구성된 배열 A를 생각해 봅시다:

  A[0] = 23171
  A[1] = 21011
  A[2] = 21123
  A[3] = 21366
  A[4] = 21013
  A[5] = 21367

주식을 0일에 매수하고 2일에 매도한 경우, A[2] - A[0] = 21123 - 23171 = -2048이므로 2048의 손실이 발생합니다. 4일째에 주식을 매수하고 5일째에 매도했다면 A[5] - A[4] = 21367 - 21013 = 354이므로 354의 이익이 발생합니다. 가능한 최대 수익은 356입니다. 1일차에 주식을 매수하고 5일차에 매도한 경우입니다.

함수를 작성합니다,

functino solution(A);

이 함수는 N일 연속된 기간 동안 주식의 일일 가격이 포함된 N개의 정수로 구성된 배열 A가 주어지면, 이 기간 동안 한 거래에서 가능한 최대 이익을 반환합니다. 이 함수는 이익을 얻을 수 없는 경우 0을 반환해야 합니다.

예를 들어 다음과 같은 6개의 요소로 구성된 배열 A가 주어집니다:

  A[0] = 23171
  A[1] = 21011
  A[2] = 21123
  A[3] = 21366
  A[4] = 21013
  A[5] = 21367

이면 함수는 위에서 설명한 대로 356을 반환해야 합니다.

다음 가정에 대한 효율적인 알고리즘을 작성합니다:

• N은 [0..400,000] 범위 내의 정수입니다;
• 배열 A의 각 요소는 [0..200,000] 범위 내의 정수입니다.

문제 접근

가장 작은 값을 기준으로 배열을 순회하면서 큰 수익을 비교하면서 저장한다.

가장 작은 값을 기준으로 하는 이유는 값 - 가장 작은 값 일때 가장 큰 수익이 나기 때문이다.

1. index 1 부터 배열을 순회한다.
2. 순회하면서 수익을 계산한다.
3. 현재 가장 작은 값이 현재 배열의 index인 값보다 크다면 가장 작은 값을 교체 한다.

function solution(A) {
    if (A.length < 2) {
        return 0;
    }
    
    let minPrice = A[0];
    let result = 0;
    let temp = 0;

    for (let i = 1; i < A.length; i++) {
        temp = A[i] - minPrice;

        if (A[i] < minPrice) {
            minPrice = A[i];
        }

        result = Math.max(temp, result);
    }

    if (result < 0) {
        return 0;
    }

    return result;
}